import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class LockingTree {
    LockNode[] lockNodes;

    int[] parent;

    class LockNode {
        Integer lockUser;
        Integer node;
        List<Integer> descendantNodes = new ArrayList<>();

        public LockNode(Integer node) {
            this.node = node;
        }
    }

    boolean unlockDescendantNodes(LockNode lockNode){
        boolean haveLock = false;
        if(lockNode.lockUser != null){
            lockNode.lockUser = null;
            haveLock = true;
        }
        for (Integer descInd : lockNode.descendantNodes) {
            haveLock |= unlockDescendantNodes(lockNodes[descInd]);
        }
        return haveLock;
    }

    boolean isAncestorLock(LockNode lockNode){
        for(int tmpInd = lockNode.node; tmpInd != -1; tmpInd = parent[tmpInd]){
            if(lockNodes[tmpInd].lockUser != null){
                return true;
            }
        }
        return false;
    }

    void initLockingTree(int[] parent){
        lockNodes = new LockNode[parent.length];
        for (int i = 0; i < parent.length; i++) {
            lockNodes[i] = new LockNode(i);
        }
        for (int i = 0; i < parent.length; i++) {
            if(parent[i] != -1){
                lockNodes[parent[i]].descendantNodes.add(i);
            }
        }
    }

    public LockingTree(int[] parent) {
        this.parent = parent;
        initLockingTree(parent);
    }

    public boolean lock(int num, int user) {
        LockNode lockNode = lockNodes[num];
        if(lockNode.lockUser == null){
            lockNode.lockUser = user;
            return true;
        }
        return false;
    }

    public boolean unlock(int num, int user) {
        LockNode lockNode = lockNodes[num];
        if(lockNode.lockUser != null && lockNode.lockUser == user){
            lockNode.lockUser = null;
            return true;
        }
        return false;
    }

    public boolean upgrade(int num, int user) {
        LockNode lockNode = lockNodes[num];
        if(!isAncestorLock(lockNode)){
            if(unlockDescendantNodes(lockNode)){
                lockNode.lockUser = user;
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        LockingTree lockingTree = new LockingTree(new int[]{-1,0,0,1,1,2,2});
        System.out.println(lockingTree.lock(2,2));
        System.out.println(lockingTree.unlock(2,3));
        System.out.println(lockingTree.unlock(2,2));
        System.out.println(lockingTree.lock(4,5));
        System.out.println(lockingTree.upgrade(0, 1));
        System.out.println(lockingTree.lock(0,1));
        System.out.println(lockingTree);
    }
}
